The Storage vs Repair-Bandwidth Trade-off for Clustered Storage Systems

摘要

We study a generalization of the setting of regenerating codes, motivated byapplications to storage systems consisting of clusters of storage nodes. Thereare $n$ clusters in total, with $m$ nodes per cluster. A data file is coded andstored across the $mn$ nodes, with each node storing $\alpha$ symbols. Foravailability of data, we require that the file be retrievable by downloadingthe entire content from any subset of $k$ clusters. Nodes represent entitiesthat can fail. We distinguish between intra-cluster and inter-cluster bandwidth(BW) costs during node repair. Node-repair in a cluster is accomplished bydownloading $\beta$ symbols each from any set of $d$ other clusters, dubbedremote helper clusters, and also up to $\alpha$ symbols each from any set of$\ell$ surviving nodes, dubbed local helper nodes, in the host cluster. Wefirst identify the optimal trade-off between storage-overhead and inter-clusterrepair-bandwidth under functional repair, and also present optimal exact-repaircode constructions for a class of parameters. The new trade-off is strictlybetter than what is achievable via space-sharing existing coding solutions,whenever $\ell > 0$. We then obtain sharp lower bounds on the necessaryintra-cluster repair BW to achieve optimal trade-off. Under functional repair,random linear network codes (RLNCs) simultaneously optimize usage of bothinter- and intra-cluster repair BW; simulation results based on RLNCs suggestoptimality of the bounds on intra-cluster repair-bandwidth. Our bounds revealthe interesting fact that, while it is beneficial to increase the number oflocal helper nodes $\ell$ in order to improve thestorage-vs-inter-cluster-repair-BW trade-off, increasing $\ell$ not onlyincreases intra-cluster BW in the host-cluster, but also increases theintra-cluster BW in the remote helper clusters.